home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / mac / hypercrd / hc1_2_x / fretext1.sit / Free Text Source Code / indexFile 0.72.c < prev    next >
Text File  |  1990-01-28  |  41KB  |  1,668 lines
  1. /* new indexFile XFCN for Free Text projects
  2.  * copyright 1990 - Mark Zimmermann
  3.  *
  4.  * call the XFCN as 'indexFile()' ... it returns with nothing
  5.  * if all goes well, and an error message (if possible) otherwise...
  6.  *
  7.  * For further information, write:
  8.  *    Mark ^Zimmermann
  9.  *    P.O.Box 8310
  10.  *    Silver Spring, MD  20907
  11.  *    USA
  12.  *
  13.  * Be sure to enclose a STAMPED, SELF-ADDRESSED ENVELOPE if you want
  14.  * to receive a timely reply!
  15.  *
  16.  * Electronic addresses:
  17.  *     science@nems.dt.navy.mil
  18.  *     [75066,2044] CompuServe
  19.  */
  20.  
  21.  
  22. /* header files to include...
  23.  */
  24.  
  25. #include <MacTypes.h>
  26. #include <EventMgr.h>
  27. #include <OSUtil.h>
  28. #include <FileMgr.h>
  29. #include <WindowMgr.h>
  30. #include <StdFilePkg.h>
  31. #include <HyperXCmd.h>
  32. #include <SetUpA4.h>
  33.  
  34. /* sort on 28 characters --  long enough to avoid truncation of most real
  35.  * words, and short enough to save some space in the *.k files
  36.  */
  37. #define KEY_LENGTH  28
  38.  
  39. /* my standard structure for the index_keys file
  40.  */
  41. typedef struct
  42.   {
  43.     char kkey[KEY_LENGTH];
  44.     long ccount;
  45.   }  KEY_REC;
  46.  
  47. /* my standard structure for simple I/O buffers ...
  48.  */
  49. typedef struct
  50.   {
  51.     char *zbufbase;
  52.     char *zbufp;
  53.     long zbufcounter;
  54.     long zbufsize;
  55.     int  zbuffilep;
  56.     int  zbufitemsize;
  57.   }  ZBUF;
  58.  
  59.  
  60. /* merge this many files at each stage of the merging operation for index
  61.  * building ... 2 means a binary merge, etc. ... one needs to have at least
  62.  * 5 + 2 * NMERGE I/O buffers around:  for each of NMERGE files, there is
  63.  * a *.k keys file and a *.p pointers file; plus there must be a single
  64.  * output *.k and a single output *.p file; plus there is the need for stdin,
  65.  * stdout, and stderr to be open as well.  Thus, I have found that a 4-way
  66.  * merge (NMERGE = 4) works pretty nicely....
  67.  */
  68. #define NMERGE 4
  69.  
  70. #ifndef TRUE
  71. #define TRUE   1
  72. #endif
  73.  
  74. #ifndef FALSE
  75. #define FALSE  0
  76. #endif
  77.  
  78. #ifndef NULL 
  79. #define NULL   0
  80. #endif
  81.  
  82. #ifndef EOF
  83. #define EOF  (-1)
  84. #endif
  85.  
  86.  
  87.  
  88. /* --------------function prototypes ----------------------- */
  89.  
  90.  
  91. pascal void main (XCmdBlockPtr paramPtr);
  92. int zGetFile (Str255 *fileNamePtr, int *volRefNumPtr);
  93. void returnErrorMsg (XCmdBlockPtr paramPtr, char *msg);
  94. void give_msg (char *msg);
  95. void beepWait (void);
  96. long atol (char *s);
  97. int putNum (char *ans, long num);
  98. int strlen (char *s);
  99. char *strcpy (char *s1, char *s2);
  100. void create_zbuffer (int n, long bufsize, int buffile, int bufitemsize,
  101.                         ZBUF zbuffer[]);
  102. char *next_input_item (int n, ZBUF zbuffer[]);
  103. void load_zbuffer (int n, ZBUF zbuffer[]);
  104. char *next_output_item (int n, ZBUF zbuffer[]);
  105. void flush_zbuffer (int n, ZBUF zbuffer[]);
  106. int build_indices (long zbufsiz, int doc_file, int vRef0, int pass_number);
  107. void init_filter_table (void);
  108. char *make_buf (long bufsiz);
  109. long load_doc_buffer (char *doc, long doc_bufsiz, char **ptr, int doc_file);
  110. int zgetc (int refNum);
  111. char *strncpy(char *s1, char *s2, int n);
  112. void nway_merge_kpfiles (int ink[], int inp[], int outk, int outp, int n,
  113.                             long zbufsiz);
  114. void copy_ptr_recs (int inzbuf, long count, int outzbuf, ZBUF zbuffer[]);
  115. void copy_key_rec (char *kkey, long ccount, int outzbuf, ZBUF zbuffer[]);
  116. int merge_not_finished (KEY_REC *kr[], int n);
  117. int smallest_key (KEY_REC *kr[], int n);
  118. int merge_indices (long zbufsiz, int doc_file, int vRef0,
  119.             int file_number, int generation_number, Str255 doc_filename);
  120. long write_sorted_files (char *doc, char **ptr, long nwords, long offset,
  121.         long zbufsiz, int pass_number, int vRef0);
  122. int is_new_word (char *w0, char *w1);
  123. void write_new_key (char *p, char *kp);
  124. long file_size (int refnum);
  125. int open_inkfile (int file_num, int vRef0, int generation_number);
  126. int open_inpfile (int file_num, int vRef0, int generation_number);
  127. void fix_oddball_file_name (int vRef0, int generation_number,
  128.             int file_number);
  129. void fix_final_file_names (Str255 doc_filename, int vRef0,
  130.             int generation_number);
  131. int open_outkfile (int vRef0, int generation_number, int file_number);
  132. int open_outpfile (int vRef0, int generation_number, int file_number);
  133. void remove_used_infiles (int n, int vRef0, int generation_number,
  134.             int file_number);
  135. void close_infiles (int ink[], int inp[], int n);
  136. int open_kfile (int vRef0, int pass_number);
  137. int open_pfile (int vRef0, int pass_number);
  138. long zftell (int refnum);
  139. void zqsort (char **first, char **last);
  140. int compare_ptrs (char **p1, char **p2);
  141. int zstrcmp (char *s1, char *s2);
  142.  
  143.  
  144. /* standard table to filter lower-case characters to capitals (if possible)
  145.  * for sorting into alphabetical order ... my best estimates of what to
  146.  * do for foreign characters in the Apple character set ... consider
  147.  * using international utilities someday to do the sorting better...
  148.  */
  149.  
  150. char filter_table[256] =
  151.   {       0,   0,   0,   0,   0,   0,   0,   0,
  152.        0,   0,   0,   0,   0,   0,   0,   0,
  153.          0,   0,   0,   0,   0,   0,   0,   0,
  154.          0,   0,   0,   0,   0,   0,   0,   0,
  155.        0,   0,   0,   0,   0,   0,   0,   0,
  156.        0,   0,   0,   0,   0,   0,   0,   0,
  157.      '0', '1', '2', '3', '4', '5', '6', '7',
  158.      '8', '9',   0,   0,   0,   0,   0,   0,
  159.        0, 'A', 'B', 'C', 'D', 'E', 'F', 'G',
  160.      'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
  161.      'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
  162.      'X', 'Y', 'Z',   0,   0,   0,   0,   0,
  163.        0, 'A', 'B', 'C', 'D', 'E', 'F', 'G',
  164.      'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
  165.      'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
  166.      'X', 'Y', 'Z',   0,   0,   0,   0,   0,
  167.     0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,
  168.     0xCB,0x89,0x80,0xCC,0x81,0x82,0x83,0x8F,
  169.     0x90,0x91,0x92,0x93,0x94,0x95,0x84,0x97,
  170.     0x98,0x99,0x85,0xCD,0x9C,0x9D,0x9E,0x86,
  171.        0,   0,   0,   0,   0,   0,   0,0xA7,
  172.        0,   0,   0,   0,   0,   0,0xAE,0xAF,
  173.        0,   0,   0,   0,   0,0xB5,0xC6,0xB7,
  174.     0xB8,0xB8,   0,0xBB,0xBC,0xBD,0xAE,0xAF,
  175.        0,   0,   0,   0,   0,   0,0xC6,   0,
  176.        0,   0,   0,0xCB,0xCC,0xCD,0xCE,0xCE,
  177.        0,   0,   0,   0,   0,   0,   0,   0,
  178.     0xD8,   0,   0,   0,   0,   0,   0,   0,
  179.        0,   0,   0,   0,   0,   0,   0,   0,
  180.        0,   0,   0,   0,   0,   0,   0,   0,
  181.        0,   0,   0,   0,   0,   0,   0,   0,
  182.        0,   0,   0,   0,   0,   0,   0,   0  } ;
  183.  
  184.  
  185. /* ----------------------main program------------------------- */
  186.  
  187. pascal void main (paramPtr)
  188.   XCmdBlockPtr paramPtr;
  189.   {
  190.     Str255 doc_filename;
  191.     char info[128];
  192.     Ptr testzbufsiz;
  193.     WindowRecord w_record;
  194.     WindowPtr info_window;
  195.     Rect b_rect;
  196.     Handle answer;
  197.     int doc_file, vRef0, pass_number, generation_number,
  198.         prev_gen_number, file_number, i;
  199.     long zbufsiz, doc_filesize, grow;
  200.  
  201.     RememberA0();
  202.     SetUpA4();
  203.     
  204.     if (paramPtr->paramCount != 0)
  205.       {
  206.          returnErrorMsg (paramPtr,
  207.               "{Sorry, wrong number of parameters in indexFile call!}");
  208.           RestoreA4();
  209.           return;
  210.       }
  211.  
  212.     /* see how much memory we can get for our zbuffers ... */
  213.     MaxApplZone();
  214.     zbufsiz = MaxMem (&grow) - 32768;
  215.     zbufsiz /=  (2 * NMERGE + 2);
  216.     zbufsiz = zbufsiz - zbufsiz % (sizeof(KEY_REC) * sizeof(long));
  217.      
  218.     if (zbufsiz < sizeof(KEY_REC) * sizeof(long) ||
  219.         (testzbufsiz = NewPtr (zbufsiz * (2 * NMERGE + 2))) == NULL)
  220.       {
  221.          returnErrorMsg (paramPtr,
  222.               "{Sorry, not enough free memory to build an index!}");
  223.           RestoreA4();
  224.           return;
  225.       }
  226.       DisposPtr (testzbufsiz);
  227.  
  228.     /* set up a window to give user feedback during indexing */
  229.     b_rect.top = 30;
  230.     b_rect.left = 12;
  231.     b_rect.bottom = 332;
  232.     b_rect.right = 500;
  233.     info_window = NewWindow (&w_record, &b_rect, "\p", (Boolean)1,
  234.         dBoxProc, (WindowPtr)-1, (Boolean)0, (long)0);
  235.     ShowWindow (info_window);
  236.     SetPort (info_window);
  237.     TextFont (0);
  238.     give_msg ("\pGreetings!  Please choose a file to be indexed...");
  239.  
  240.     if (! zGetFile (&doc_filename, &vRef0))
  241.       {
  242.         CloseWindow (info_window);
  243.           RestoreA4();
  244.         return;
  245.       }
  246.     
  247.     i = FSOpen (doc_filename, vRef0, &doc_file);
  248.     if (i != noErr && i != opWrErr)
  249.       {
  250.         give_msg ("\pSorry, error opening the file!  Click mouse to exit...");
  251.         beepWait ();
  252.         CloseWindow (info_window);
  253.           RestoreA4();
  254.           return;
  255.       }
  256.     
  257.     give_msg ("\pBeginning to build index subfiles ╤ please be patient...");
  258.     
  259.     pass_number = 0;
  260.     while (build_indices (zbufsiz, doc_file, vRef0, pass_number))
  261.         ++pass_number;
  262.     
  263.     if (pass_number == 0)
  264.           give_msg ("\pNo data to index!");
  265.     else
  266.       {
  267.           if (pass_number > 1)
  268.             give_msg ("\pBeginning merge generation #1 ╤ please be patient...");
  269.  
  270.         file_number = 0;
  271.         generation_number = 0;
  272.         do
  273.           {
  274.             prev_gen_number = generation_number;
  275.             generation_number = merge_indices (zbufsiz, doc_file, vRef0,
  276.                         file_number, generation_number, doc_filename);
  277.             if (generation_number == prev_gen_number)
  278.                 file_number += NMERGE;
  279.             else
  280.                 file_number = 0;
  281.           }
  282.         while (generation_number >= 0);
  283.         give_msg ("\pIndexing completed!");
  284.       }
  285.  
  286.     FSClose (doc_file);
  287.     give_msg ("\pClick mouse to exit...");
  288.     beepWait ();
  289.     CloseWindow (info_window);
  290.     RestoreA4();
  291.     return;
  292.   }
  293.  
  294.  
  295. /* this routine, adapted from the Lightspeed C 'MiniEdit' example, does
  296.  * the standard files dialog routine to get the name of the file to be indexed
  297.  * for the database; other file names are gotten from that by putting
  298.  * a '.k' or a '.p' at the end.  This routine returns 1 if all is well,
  299.  * or 0 if the user cancels out...
  300.  *
  301.  * note that the file type is not used here, though a parameter has to be
  302.  * passed (I think) to SFGetFile()....
  303.  */
  304.  
  305. int zGetFile (fileNamePtr, volRefNumPtr)
  306.   Str255 *fileNamePtr;
  307.   int *volRefNumPtr;
  308.   {
  309.     SFTypeList myFileTypes;
  310.     Point SFGwhere;
  311.     SFReply myReply;
  312.     register int i;
  313.  
  314.     SFGwhere.v = 90;
  315.     SFGwhere.h = 82;
  316.     myFileTypes[0] = 'TEXT';    /* this isn't actually used */
  317.     
  318.     SFGetFile (SFGwhere, "\p", 0L, -1, myFileTypes, 0L, &myReply);
  319.     
  320.     if (myReply.good)
  321.       {
  322.         for (i = *myReply.fName; i >= 0; --i)
  323.             (*fileNamePtr)[i] = myReply.fName[i];
  324.         *volRefNumPtr = myReply.vRefNum;
  325.         return (1);
  326.       }
  327.     else
  328.         return (0);
  329.   }
  330.  
  331.  
  332. /* function to set the return value of the XFCN to a chosen error msg;
  333.  * if there isn't enough free memory to give us a Handle to the msg,
  334.  * beep a bit more and then return!
  335.  */
  336.  
  337. void returnErrorMsg (paramPtr, msg)
  338.   XCmdBlockPtr paramPtr;
  339.   char *msg;
  340.   {
  341.     Handle answer;
  342.     int msgLength;
  343.     
  344.     SysBeep (10);
  345.     msgLength = strlen (msg);
  346.     if ((answer = NewHandle (1 + msgLength)) == NULL)
  347.       {
  348.         SysBeep (10);
  349.         SysBeep (10);
  350.         return;
  351.       }
  352.  
  353.     strcpy (*answer, msg);
  354.     paramPtr->returnValue = answer;
  355.     return;
  356.   }
  357.  
  358.  
  359. /* tiny routine to put a message into my message window.... takes in a
  360.  * PASCAL type string and displays it decently, scrolling text up....
  361.  */
  362.  
  363. void give_msg (msg)
  364.   char *msg;
  365.   {
  366.     Rect b_rect;
  367.     RgnHandle theRgn;
  368.     
  369.     b_rect.top = b_rect.left = 0;
  370.     b_rect.bottom = 302;
  371.     b_rect.right = 488;
  372.     
  373.     theRgn = NewRgn ();
  374.     ScrollRect (&b_rect, 0, -15, theRgn);
  375.     DisposeRgn (theRgn);
  376.     
  377.     MoveTo (4, 295);
  378.     DrawString (msg);
  379.     
  380.     return;
  381.   }
  382.  
  383.  
  384. /* function to beep and then wait for a mouse click before returning...
  385.  * delay for 2 ticks to debounce the mouse button a bit .... flush
  386.  * events to avoid spurious clicks hanging around....
  387.  */
  388.  
  389. void beepWait ()
  390.   {
  391.       long tickcount;
  392.  
  393.       SysBeep (10);
  394.       while (! Button())
  395.         ;
  396.     Delay (2L, &tickcount);
  397.     while (Button())
  398.         ;
  399.     Delay (2L, &tickcount);
  400.     FlushEvents (everyEvent, 0);
  401.     return;
  402.   }
  403.  
  404.  
  405. /* function to convert alphabetic string to a long integer ... 
  406.  */
  407.  
  408. long atol (s)
  409.   register char *s;
  410.   {
  411.     register char signflag = 0;
  412.     register long r = 0;
  413.  
  414.     while ((*s == ' '))
  415.         s++;
  416.         
  417.     if (*s == '-')
  418.       {
  419.         signflag = 1;
  420.         s++;
  421.       }
  422.     else if (*s == '+')
  423.          s++;
  424.  
  425.     while (*s >= '0' && *s <= '9') 
  426.         r = r * 10 + (*s++ - '0');
  427.     
  428.     return (signflag ? -r : r);
  429. }
  430.  
  431.  
  432.  
  433. /* function to convert a number into a string and put it into the chosen
  434.  * target place ... returns the number of characters stored ...
  435.  * based on K&R p. 60 example of itoa()....
  436.  *
  437.  * ---> note, there is NO TERMINAL '\0' in the string that is built!!!! <---
  438.  */
  439.  
  440. int putNum (ans, num)
  441.   register char *ans;
  442.   register long num;
  443.   {
  444.     register int i, j;
  445.     int s, result;
  446.     
  447.     i = 0;
  448.     s = 1;
  449.     if (num < 0)
  450.       {
  451.         num = -num;
  452.         s = -1;
  453.       }
  454.     
  455.     do
  456.           ans[i++] = num % 10 + '0';
  457.     while ((num /= 10) > 0);
  458.     
  459.     if (s < 0)
  460.         ans[i++] = '-';
  461.     result = i;
  462.     
  463.     for (--i, j = 0; j < i; ++j, --i)
  464.       {
  465.           s = ans[i];
  466.           ans[i] = ans[j];
  467.           ans[j] = s;
  468.       }
  469.  
  470.     return (result);
  471.   }
  472.  
  473.  
  474. /* function to determine the length of a string ... standard thing,
  475.  * adapted from K&R p.98 ....
  476.  */
  477.  
  478. int strlen (s)
  479.   register char *s;
  480.   {
  481.     char *s0 = s;
  482.  
  483.     while (*s++)
  484.         ;
  485.     return (s - s0 - 1);
  486.   }
  487.  
  488.  
  489. /* function to copy a string from one place to another, in a rather
  490.  * obvious fashion ... adapted from K&R p.101 ....
  491.  */
  492.  
  493. char *strcpy (s1, s2)
  494.   register char *s1, *s2;
  495.   {
  496.     char *s = s1;
  497.     
  498.     while (*s1++ = *s2++)
  499.         ;
  500.     return (s);
  501.   }
  502.  
  503.  
  504. /* -------------------buffer-related functions-----------------*/
  505.  
  506. /* function to create a zbuffer and set its parameters appropriately
  507.  */
  508.  
  509. void create_zbuffer (n, bufsize, buffile, bufitemsize, zbuffer)
  510.   int n, bufitemsize;
  511.   long bufsize;
  512.   int buffile;
  513.   ZBUF zbuffer[];
  514.   {
  515.     zbuffer[n].zbufbase = make_buf (bufsize);
  516.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  517.     zbuffer[n].zbufcounter = 0;
  518.     zbuffer[n].zbufsize = bufsize;
  519.     zbuffer[n].zbuffilep = buffile;
  520.     zbuffer[n].zbufitemsize = bufitemsize;
  521.   }
  522.  
  523.  
  524. /* function to return a pointer to the next item in a chosen input
  525.  * buffer 'n'; it reloads the buffer if necessary ... returns NULL
  526.  * pointer when there's nothing left in the file ...
  527.  */
  528.  
  529. char *next_input_item (n, zbuffer)
  530.   int n;
  531.   ZBUF zbuffer[];
  532.   {
  533.     char *result;
  534.     
  535.     if (zbuffer[n].zbufcounter == 0)
  536.         load_zbuffer (n, zbuffer);
  537.     
  538.     zbuffer[n].zbufcounter -= zbuffer[n].zbufitemsize;
  539.     if (zbuffer[n].zbufcounter >= 0)
  540.       {
  541.         result = zbuffer[n].zbufp;
  542.         zbuffer[n].zbufp += zbuffer[n].zbufitemsize;
  543.         return (result);
  544.       }
  545.     else
  546.         return (NULL);
  547.   }
  548.  
  549.  
  550. /* function to load the nth zbuffer appropriately ... it resets the buffer
  551.  * pointers, etc. ... 
  552.  */
  553.  
  554. void load_zbuffer (n, zbuffer)
  555.   int n;
  556.   ZBUF zbuffer[];
  557.   {
  558.     long nread;
  559.     OSErr err;
  560.  
  561.     nread = zbuffer[n].zbufsize;
  562.     err = FSRead (zbuffer[n].zbuffilep, &nread, zbuffer[n].zbufbase);
  563.  
  564.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  565.     zbuffer[n].zbufcounter = nread;
  566.     
  567.     if (err != noErr && err != eofErr)
  568.       {
  569.         give_msg ("\pSorry, fatal error loading buffer -- click mouse to exit, then reboot!");
  570.         beepWait ();
  571.           RestoreA4();
  572.         ExitToShell ();
  573.       }
  574.     
  575.     return;
  576.   }
  577.  
  578.  
  579. /* function to return a pointer to the right place to store the next
  580.  * output item for the nth zbuffer ... when the buffer becomes full,
  581.  * it flushes it to disk, resets pointers, etc.
  582.  */
  583.  
  584. char *next_output_item (n, zbuffer)
  585.   int n;
  586.   ZBUF zbuffer[];
  587.   {
  588.     char *result;
  589.  
  590.     if (zbuffer[n].zbufcounter == zbuffer[n].zbufsize)
  591.         flush_zbuffer (n, zbuffer);
  592.     
  593.     result = zbuffer[n].zbufp;
  594.     zbuffer[n].zbufp += zbuffer[n].zbufitemsize;
  595.     zbuffer[n].zbufcounter += zbuffer[n].zbufitemsize;
  596.     return (result);
  597.   }
  598.  
  599.  
  600. /* function to flush out a zbuffer to the disk ... 
  601.  */
  602.  
  603. void flush_zbuffer (n, zbuffer)
  604.   int n;
  605.   ZBUF zbuffer[];
  606.   {
  607.     long chars_written;
  608.     
  609.     if (zbuffer[n].zbufcounter == 0)
  610.         return;
  611.  
  612.     chars_written = zbuffer[n].zbufcounter;
  613.     if (FSWrite (zbuffer[n].zbuffilep, &chars_written,
  614.                 zbuffer[n].zbufbase) != noErr || chars_written == 0)
  615.       {
  616.         give_msg ("\pSorry, fatal error flushing buffer -- click mouse to exit, then reboot!");
  617.         beepWait ();
  618.           RestoreA4();
  619.         ExitToShell ();
  620.       }
  621.     
  622.     zbuffer[n].zbufp = zbuffer[n].zbufbase;
  623.     zbuffer[n].zbufcounter = 0;
  624.   }
  625.   
  626.  
  627. /* ------------------index-building functions------------------*/
  628.  
  629. int build_indices (zbufsiz, doc_file, vRef0, pass_number)
  630.   long zbufsiz;
  631.   int doc_file, vRef0, pass_number;
  632.   {
  633.     long doc_bufsiz, offset, nwords, ndistinctwords;
  634.     char *doc, **ptr, info[128];
  635.     int i;
  636.  
  637.     doc_bufsiz = 2 * NMERGE * zbufsiz / 3 - KEY_LENGTH;
  638.     doc = make_buf (doc_bufsiz + KEY_LENGTH);
  639.     
  640.     ptr = (char **)make_buf (doc_bufsiz * 2);
  641.  
  642.     offset = zftell (doc_file);    
  643.     
  644.     nwords = load_doc_buffer (doc, doc_bufsiz, ptr, doc_file);
  645.  
  646.     if (nwords == 0)
  647.       {
  648.         DisposPtr (doc);
  649.         DisposPtr (ptr);
  650.         return (FALSE);
  651.       }
  652.     
  653.     zqsort (ptr, ptr + nwords);
  654.  
  655.     ndistinctwords = write_sorted_files (doc, ptr, nwords, offset, zbufsiz,
  656.                             pass_number, vRef0);
  657.     
  658.     DisposPtr (doc);
  659.     DisposPtr (ptr);
  660.  
  661.     strncpy (info + 1, "Index subfile #", 15);
  662.     i = 16 + putNum (info + 16, pass_number + 1);
  663.     strncpy (info + i, ":  ", 3);
  664.     i += 3;
  665.     i += putNum (info + i, nwords);
  666.     strncpy (info + i, " total words, ", 14);
  667.     i += 14;
  668.     i += putNum (info + i, ndistinctwords);
  669.     strncpy (info + i, " distinct words.", 16);
  670.     i += 16;
  671.     info[0] = i - 1;
  672.     give_msg (info);
  673.     
  674.     return (TRUE);
  675.   }
  676.  
  677.  
  678. /* ---------functions to load text from document file filter it-------- */
  679.  
  680.  
  681. /* function to create a buffer for me to use...
  682.  */
  683.  
  684. char *make_buf (bufsiz)
  685.   long bufsiz;
  686.   {
  687.     char *buf;
  688.     
  689.     buf = NewPtr (bufsiz);
  690.  
  691.     if (buf == 0)
  692.       {
  693.         give_msg ("\pSorry, fatal error creating buffer -- click mouse to exit, then reboot!");
  694.         beepWait ();
  695.           RestoreA4();
  696.         ExitToShell ();
  697.       }
  698.     
  699.     return (buf);
  700.   }
  701.  
  702.  
  703. /* function to load the document buffer ... bring in doc_bufsiz
  704.  * characters, and then enough more to finish out the final word,
  705.  * followed by a terminal delimiter .... as the characters are scanned
  706.  * filter them appropriately (change delimiters to '\0's) and
  707.  * build the pointer array in memory to the first character of each
  708.  * word ... return the total number of words that were
  709.  * read in to the buffer (zero if we're finished with the file)
  710.  *
  711.  * ... note that one must be sure to pull in and throw away
  712.  * any excess characters beyond KEY_LENGTH in the final word, so that
  713.  * the remaining fragment doesn't show up as the first "word" in the
  714.  * next chunk of the file....
  715.  *
  716.  * For maximum speed and efficiency, use a hybrid approach:  do a
  717.  * big buffer-sized chunk of the file first, then take one character at
  718.  * a time to finish off....
  719.  */
  720.  
  721. long load_doc_buffer (doc, doc_bufsiz, ptr, doc_file)
  722.   register char *doc, **ptr;
  723.   long doc_bufsiz;
  724.   int doc_file;
  725.   {
  726.     int  i, err;
  727.     register int c, in_a_word = FALSE;
  728.     char **ptr0, *end_doc_buf;
  729.      
  730.      ptr0 = ptr;
  731.      
  732.      err = FSRead (doc_file, &doc_bufsiz, doc);
  733.      if (err != noErr && err != eofErr)
  734.       {
  735.         give_msg ("\pSorry, fatal error reading text -- click mouse to exit, then reboot!");
  736.         beepWait ();
  737.           RestoreA4();
  738.         ExitToShell ();
  739.       }
  740.  
  741.      end_doc_buf = doc + doc_bufsiz;
  742.      
  743.      while (doc < end_doc_buf)
  744.       {
  745.         c = filter_table[*(unsigned char *)doc];
  746.  
  747.         if (c == '\0')
  748.             in_a_word = FALSE;
  749.          else if (! in_a_word)
  750.           {
  751.             *ptr++ = doc;
  752.             in_a_word = TRUE;
  753.           }
  754.  
  755.          *doc++ = c;
  756.        }
  757.      
  758.      if (err != eofErr && doc == end_doc_buf && in_a_word)
  759.       {
  760.           for (i = 0; i < KEY_LENGTH; ++i)
  761.            {
  762.              c = zgetc (doc_file);
  763.              if (c == EOF)
  764.                {
  765.                  *doc++ = '\0';
  766.                  break;
  767.                }
  768.              c = filter_table[c];
  769.              if (c == '\0')
  770.                {
  771.                  *doc++ = '\0';
  772.                  break;
  773.                }
  774.              *doc++ = c;
  775.            }
  776.          if (i == KEY_LENGTH)
  777.              while ((c = zgetc (doc_file)) != EOF && filter_table[c])
  778.                 ;
  779.        }
  780.      
  781.      return (ptr - ptr0);
  782.   }
  783.  
  784.  
  785. /* my function to replace getc() ... give up and call it EOF on any error
  786.  * at all, at this point! ... note also that we must return the UNSIGNED
  787.  * character read in, to handle Mac special characters properly....
  788.  */
  789.  
  790. int zgetc (refNum)
  791.   int refNum;
  792.   {
  793.       unsigned char readbuf[1];
  794.       long count = 1;
  795.       
  796.     if (FSRead (refNum, &count, readbuf) == noErr)
  797.         return (readbuf[0]);
  798.     else
  799.         return (EOF);
  800.   }
  801.  
  802.  
  803. /* function to copy a string of length up to n from s2 to s1....
  804.  */
  805.  
  806. char *strncpy (s1, s2, n)
  807.   register char *s1, *s2;
  808.   register int n;
  809.   {
  810.     char *s0 = s1;
  811.     
  812.     if (n > 0)
  813.     {
  814.         while (n-- && (*s1++ = *s2++));
  815.     
  816.         while (n > 0)
  817.         {    /* pad out to n chars -- H&S specs it this way... */
  818.         
  819.             *s1++ = '\0';
  820.             n--;
  821.         }
  822.     }
  823.         
  824.     return (s0);
  825. }
  826.  
  827.  
  828. /* ------functions to merge key and ptr files-------------------- */
  829.  
  830.  
  831. /* function to do the real work of merging sorted k & p
  832.  * files into a single sorted file...
  833.  *
  834.  * Procedure is as follows:
  835.  *
  836.  *    Compare the current key records from each of the N files to be merged.
  837.  *    Take the smallest of the keys (or, if there is a tie, take the one
  838.  *    from the earlier file number) and write its pointer records out to
  839.  *    the *.p file for the next generation.  If the key is a new one, that
  840.  *    is, if it differs from the previous key, write out the previous key
  841.  *    word and the value for cumulative_counts to the *.k file, and reset
  842.  *    the previous key's value to that of the current key.  Then repeat
  843.  *    this whole procedure, until all the input files are exhausted.
  844.  *
  845.  *    The above works provided that we are careful in choosing the smallest
  846.  *    key and never let a file that has been exhausted (reached EOF) win a
  847.  *    comparison.  The function smallest_key does that properly below, since
  848.  *    a file that is at EOF has returned a NULL pointer for its key_rec...
  849.  *
  850.  *  For each file, the variable prev_cc[i] holds the previous value of
  851.  *    cumulative_counts for that file, so that we can determine how
  852.  *    many ptr_recs to write out by doing a simple subtraction.
  853.  *
  854.  * Buffer numbering scheme:  the Kth input file has zbuffer #K
  855.  *    for its keys and zbuffer #(K+n) for its pointers; the output
  856.  *    buffers are zbuffers #(2*n) for keys and #(2*n+1) for pointers.
  857.  */
  858.  
  859. void nway_merge_kpfiles (ink, inp, outk, outp, n, zbufsiz)
  860.   int ink[], inp[], outk, outp, n;
  861.   long zbufsiz;
  862.   {
  863.     int i;
  864.     KEY_REC *kr[NMERGE], prev_key;
  865.     long prev_cc[NMERGE], out_cc;
  866.     ZBUF zbuffer[NMERGE * 2 + 2];    
  867.     
  868.     for (i = 0; i < n; ++i)
  869.         prev_cc[i] = 0;
  870.     out_cc = 0;
  871.     
  872.     for (i = 0; i < n; ++i)
  873.       {
  874.         create_zbuffer (i, zbufsiz, ink[i], sizeof(KEY_REC), zbuffer);
  875.         create_zbuffer (i + n, zbufsiz, inp[i], sizeof(long), zbuffer);
  876.       }
  877.     create_zbuffer (2 * n, zbufsiz, outk, sizeof(KEY_REC), zbuffer);
  878.     create_zbuffer (2 * n + 1, zbufsiz, outp, sizeof(long), zbuffer);
  879.     
  880.     for (i = 0; i < n; ++i)
  881.         kr[i] = (KEY_REC *)next_input_item (i, zbuffer);
  882.     
  883.     i = smallest_key (kr, n);
  884.     strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  885.     
  886.  
  887.     while (merge_not_finished (kr, n))
  888.       {
  889.         i = smallest_key (kr, n);
  890.         if (zstrcmp (prev_key.kkey, kr[i]->kkey))
  891.           {
  892.             copy_key_rec (prev_key.kkey, out_cc, 2 * n, zbuffer);
  893.             strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  894.           }
  895.         copy_ptr_recs (i + n, kr[i]->ccount - prev_cc[i], 2 * n + 1, zbuffer);
  896.         out_cc += kr[i]->ccount - prev_cc[i];
  897.         prev_cc[i] = kr[i]->ccount;
  898.         kr[i] = (KEY_REC *)next_input_item (i, zbuffer);
  899.       }
  900.     
  901.     copy_key_rec (prev_key.kkey, out_cc, 2 * n, zbuffer);
  902.     
  903.     flush_zbuffer (2 * n, zbuffer);
  904.     flush_zbuffer (2 * n + 1, zbuffer);
  905.     for (i = 0; i < 2 * n + 2; ++i)
  906.         DisposPtr (zbuffer[i].zbufbase);
  907.   }
  908.  
  909.  
  910. /* function to copy a chosen number of ptr_recs (longs) from one file
  911.  * to another ... used in merging two files by merge_kpfiles() above....
  912.  */
  913.  
  914. void copy_ptr_recs (inzbuf, count, outzbuf, zbuffer)
  915.   int inzbuf, outzbuf;
  916.   long count;
  917.   ZBUF zbuffer[];
  918.   {
  919.     long *inp, *outp;
  920.  
  921.     for ( ; count > 0; --count)
  922.       {
  923.         inp = (long *)next_input_item (inzbuf, zbuffer);
  924.         outp = (long *)next_output_item (outzbuf, zbuffer);
  925.         *outp = *inp;
  926.       }
  927.   }
  928.  
  929.  
  930. /* function to write a key record including kkey (key word) and ccount
  931.  * (cumulative_count) to an output file...
  932.  */
  933.  
  934. void copy_key_rec (kkey, cc, outzbuf, zbuffer)
  935.   char *kkey;
  936.   long cc;
  937.   int outzbuf;
  938.   ZBUF zbuffer[];
  939.   {
  940.     KEY_REC *outp;
  941.  
  942.     outp = (KEY_REC *)next_output_item (outzbuf, zbuffer);
  943.     strncpy (outp->kkey, kkey, KEY_LENGTH);
  944.     outp->ccount = cc;
  945.   }
  946.  
  947.  
  948. /* simple function to see if we are not yet finished with all of the input
  949.  * files coming in to the merge operation ... signified by at least one of
  950.  * the key pointers being non-NULL....
  951.  */
  952.  
  953. int merge_not_finished (kr, n)
  954.   KEY_REC *kr[];
  955.   register int n;
  956.   {
  957.     register int i;
  958.     
  959.     for (i = 0; i < n; ++i)
  960.         if (kr[i] != NULL)
  961.             return (TRUE);
  962.     
  963.     return (FALSE);
  964.   }
  965.  
  966.  
  967. /* function to determine the smallest of the n keys pointed to by the
  968.  * kr[] vector of pointers to KEY_RECs ... note that a NULL ptr ranks
  969.  * after any other...also note that in case of a tie, the smaller
  970.  * value of i is the one to return (for a stable merging sort)
  971.  */
  972.  
  973. smallest_key (kr, n)
  974.   KEY_REC *kr[];
  975.   register int n;
  976.   {
  977.     register int i, smallest;
  978.  
  979.     for (i = 0; i < n; ++i)
  980.         if (kr[i] != NULL)
  981.           {
  982.             smallest = i;
  983.             break;
  984.           }
  985.  
  986.     for (i = smallest + 1; i < n; ++i)
  987.         if (kr[i] != NULL)
  988.             if (zstrcmp (kr[smallest]->kkey, kr[i]->kkey) > 0)
  989.                 smallest = i;
  990.  
  991.     return (smallest);
  992.   }
  993.  
  994.  
  995. /* ---------------function to merge index files------------- */
  996.  
  997. /* function to merge sorted indices together repeatedly until finished
  998.  * with them all in a single set of *.k/*.p files ...
  999.  *
  1000.  * The merging strategy is straightforward enough:
  1001.  *    Let "g" denote the generation_number and "f" denote the file_number.
  1002.  *    Temporary file names begin with the letter z, which is then followed
  1003.  *    by a generation number (decimal), the letter k or p (standing for
  1004.  *    key or ptr, respectively), and then the file number (decimal).  Thus,
  1005.  *    the file "z0k0" is the keys file #0 for generation #0 (the starting,
  1006.  *    pre-merging, generation), file "z2p3" is the ptr file #3 for generation
  1007.  *    #2, etc.
  1008.  *
  1009.  * (The following discussion is specifically for a 2-way merge ... but
  1010.  * the generalization for N-way merging is straightforward.)
  1011.  *
  1012.  *    On a given call to merge_indices, the following may happen:
  1013.  *        - files zgkf/zgpf and zgk(f+1)/zgp(f+1) are merged into files
  1014.  *            z(g+1)k(f/2)/z(g+1)p(f/2), and then the parent files are
  1015.  *            deleted;
  1016.  *        - file zgkf isn't found, which means we are done with this
  1017.  *            generation and must go on to the next;
  1018.  *        - file zgk(f+1) isn't found, which means that either we are
  1019.  *            completely done with the merging work (if f=0) and just
  1020.  *            have to rename the files zgkf/zgpf into the correct final
  1021.  *            names (that is, doc_filename.k/doc_filename.p), or else
  1022.  *            (if f>0) we have an odd number of files for this level
  1023.  *            of merging, and therefore just have to rename zgkf/zgpf
  1024.  *            to z(g+1)k(f/2)/z(g+1)p(f/2).
  1025.  *
  1026.  * to work as a nice XFCN, this function returns the upcoming
  1027.  * generation_number, and lets the caller reset the file_number to zero
  1028.  * when the generation_number returned differs from the input number, or
  1029.  * increment the file_number by NMERGE when still on same generation.
  1030.  * Also, when all finished, we return an illegal (negative) generation_number
  1031.  * value....
  1032.  */
  1033.  
  1034. int merge_indices (zbufsiz, doc_file, vRef0, file_number,
  1035.                         generation_number, doc_filename)
  1036.   long zbufsiz;
  1037.   int doc_file, vRef0, file_number, generation_number;
  1038.   Str255 doc_filename;
  1039.   {
  1040.     int ink[NMERGE], inp[NMERGE], outk, outp;
  1041.     long inwords, indistinctwords, outdistinctwords;
  1042.     int i, n;
  1043.     char info[128];
  1044.     
  1045.     for (n = 0; n < NMERGE; ++n)
  1046.       {
  1047.         ink[n] = open_inkfile (file_number + n, vRef0, generation_number);
  1048.         if (ink[n] == NULL)
  1049.             break;
  1050.         inp[n] = open_inpfile (file_number + n, vRef0, generation_number);
  1051.       }
  1052.     
  1053.     if (file_number + n == 1)
  1054.       {        
  1055.         close_infiles (ink, inp, n);
  1056.         fix_final_file_names (doc_filename, vRef0, generation_number);
  1057.         return (-1);
  1058.       }
  1059.     
  1060.     if (n < 2)
  1061.       {
  1062.         if (n == 1)
  1063.           {
  1064.             close_infiles (ink, inp, n);
  1065.             fix_oddball_file_name (vRef0, generation_number, file_number);
  1066.           }
  1067.         strncpy (info + 1, "Beginning merge generation #", 28);
  1068.         i = 29 + putNum (info + 29, 2 + generation_number);
  1069.         info[0] = i - 1;
  1070.         give_msg (info);
  1071.         return (generation_number + 1);
  1072.       }
  1073.     
  1074.     outk = open_outkfile (vRef0, generation_number, file_number);
  1075.     outp = open_outpfile (vRef0, generation_number, file_number);
  1076.     
  1077.     inwords = 0;
  1078.     indistinctwords = 0;
  1079.     for (i = 0; i < n; ++i)
  1080.       {
  1081.         inwords += file_size (inp[i]) / sizeof(long);
  1082.         indistinctwords += file_size (ink[i]) / sizeof(KEY_REC);
  1083.       }
  1084.     
  1085.     nway_merge_kpfiles (ink, inp, outk, outp, n, zbufsiz);
  1086.     
  1087.     outdistinctwords = file_size (outk) / sizeof(KEY_REC);
  1088.  
  1089.     strncpy (info + 1, "Merge #", 7);
  1090.     i = 8 + putNum (info + 8, 1 + file_number / NMERGE);
  1091.     strncpy (info + i, ":  ", 3);
  1092.     i += 3;
  1093.     i += putNum (info + i, inwords);
  1094.     strncpy (info + i, " total words, ", 14);
  1095.     i += 14;
  1096.     i += putNum (info + i, indistinctwords);
  1097.     strncpy (info + i, " distinct words in, ", 20);
  1098.     i += 20;
  1099.     i += putNum (info + i, outdistinctwords);
  1100.     strncpy (info + i, " out.", 5);
  1101.     i += 5;
  1102.     info[0] = i - 1;
  1103.     give_msg (info);
  1104.     
  1105.     close_infiles (ink, inp, n);
  1106.     FSClose (outk);
  1107.     FSClose (outp);
  1108.     remove_used_infiles (n, vRef0, generation_number, file_number);
  1109.     
  1110.     return (generation_number);
  1111.   }
  1112.  
  1113.  
  1114. /* ------------file utility functions---------------------------- */
  1115.  
  1116. /* function to write out sorted k & p files based on the doc and ptr
  1117.  * arrays in memory....
  1118.  *
  1119.  * The kfile format is as described in detail elsewhere:
  1120.  *    the key word, turned into all capital letters and with spaces
  1121.  *        afterward, of fixed length KEY_LENGTH; and
  1122.  *    the cumulative count of how many words have passed before, including
  1123.  *        the current word, a long integer.
  1124.  */
  1125.  
  1126. long write_sorted_files (doc, ptr, nwords, offset, zbufsiz, pass_number,
  1127.                             vRef0)
  1128.   char *doc, **ptr;
  1129.   long nwords, offset, zbufsiz;
  1130.   int pass_number, vRef0;
  1131.   {
  1132.     int kfile, pfile;
  1133.     char *prev_word;
  1134.     KEY_REC *outk;
  1135.     long *outp, i;
  1136.     ZBUF zbuffer[2];
  1137.     
  1138.     if (nwords == 0)
  1139.         return;
  1140.     
  1141.     kfile = open_kfile (vRef0, pass_number);
  1142.     pfile = open_pfile (vRef0, pass_number);
  1143.     
  1144.     create_zbuffer (0, zbufsiz, kfile, sizeof(KEY_REC), zbuffer);
  1145.     create_zbuffer (1, zbufsiz, pfile, sizeof(long), zbuffer);
  1146.  
  1147.     prev_word = ptr[0];
  1148.     outk = (KEY_REC *)next_output_item (0, zbuffer);
  1149.     write_new_key (ptr[0], outk->kkey);
  1150.     
  1151.     for (i = 0; i < nwords; ++i)
  1152.       {
  1153.         if (is_new_word (prev_word, ptr[i]))
  1154.           {
  1155.             outk->ccount = i;
  1156.             outk = (KEY_REC *)next_output_item (0, zbuffer);
  1157.             write_new_key (ptr[i], outk->kkey);
  1158.             prev_word = ptr[i];
  1159.           }
  1160.         outp = (long *)next_output_item (1, zbuffer);
  1161.         *outp = (ptr[i] - doc) + offset;
  1162.       }
  1163.     outk->ccount = i;
  1164.  
  1165.     flush_zbuffer (0, zbuffer);
  1166.     flush_zbuffer (1, zbuffer);
  1167.     
  1168.     DisposPtr (zbuffer[0].zbufbase);
  1169.     DisposPtr (zbuffer[1].zbufbase);
  1170.     
  1171.     i = file_size (kfile) / sizeof(KEY_REC);
  1172.     FSClose (kfile);
  1173.     FSClose (pfile);
  1174.     
  1175.     return (i);
  1176.   }
  1177.  
  1178.  
  1179. /* function to determine if the current word is the same as or different
  1180.  * from the previous word -- if it is different, we'll need to write an
  1181.  * entry out to the key file kfile -- compare the words up to the first
  1182.  * '\0', or for a maximum distance of KEY_LENGTH, and return TRUE
  1183.  * if they differ, FALSE if they are identical that far.  Thus, a simple
  1184.  * call to zstrcmp() does the job.... but keep ours as a function instead
  1185.  * of a macro call for the moment, for safety and readability....
  1186.  */
  1187.  
  1188. int is_new_word (w0, w1)
  1189.   char *w0, *w1;
  1190.   {
  1191.     return (zstrcmp (w0, w1));
  1192.   }
  1193.  
  1194.  
  1195. /* function to write out a new key entry in the key_file:
  1196.  * KEY_LENGTH letters consisting of the key word (which will be found
  1197.  * delimited by a '\0'), followed by enough blanks to fill out the
  1198.  * record to total length KEY_LENGTH ...
  1199.  */
  1200.  
  1201. void write_new_key (p, kp)
  1202.   register char *p, *kp;
  1203.   {
  1204.     register int i, c;
  1205.  
  1206.     for (i = 0; i < KEY_LENGTH; ++i)
  1207.       {
  1208.         c = *p++;
  1209.         if (c == '\0')
  1210.             break;
  1211.         *kp++ = c;
  1212.       }
  1213.  
  1214.     for ( ; i < KEY_LENGTH; ++i)
  1215.         *kp++ = ' ';
  1216.     
  1217.     return;
  1218.   }
  1219.  
  1220.  
  1221. /* a very simple function to return the size of a file ... doesn't do any
  1222.  * error-checking -- sorry!
  1223.  */
  1224.  
  1225. long file_size (refnum)
  1226.   int refnum;
  1227.   {
  1228.     long result;
  1229.     
  1230.     GetEOF (refnum, &result);
  1231.     return (result);
  1232.   }
  1233.  
  1234.  
  1235. /* ---------------miscellaneous useful functions----------------- */
  1236.  
  1237. /* function to open an input key file for this generation and file number ...
  1238.  * note the limitation to no more than 9 generations, which with a 4-way
  1239.  * merge should be more than enough for a few years to come!  Note that
  1240.  * this function should return 0 and not give up if it attempts to open
  1241.  * a nonexistent file -- that's the signal for merge_indices() to know
  1242.  * that all of the input files have been used up....
  1243.  */
  1244.  
  1245. int open_inkfile (file_num, vRef0, generation_number)
  1246.   int file_num, vRef0, generation_number;
  1247.   {
  1248.     Str255 fname;
  1249.     int i;
  1250.     
  1251.     fname[1] = 'z';
  1252.     fname[2] = generation_number + '0';
  1253.     fname[3] = 'k';
  1254.     i = putNum ((char *)fname + 4, file_num);
  1255.     fname[0] = i + 3;
  1256.     
  1257.     if (FSOpen (fname, vRef0, &i) != noErr)
  1258.         return (NULL);
  1259.  
  1260.     return (i);
  1261.   }
  1262.  
  1263.  
  1264. /* function to open an input ptr file for this generation and file number
  1265.  */
  1266.  
  1267. int open_inpfile (file_num, vRef0, generation_number)
  1268.   int file_num, vRef0, generation_number;
  1269.   {
  1270.     Str255 fname;
  1271.     int i;
  1272.     
  1273.     fname[1] = 'z';
  1274.     fname[2] = generation_number + '0';
  1275.     fname[3] = 'p';
  1276.     i = putNum ((char *)fname + 4, file_num);
  1277.     fname[0] = i + 3;
  1278.     
  1279.     if (FSOpen (fname, vRef0, &i) != noErr)
  1280.         return (NULL);
  1281.  
  1282.     return (i);
  1283.   }
  1284.  
  1285.  
  1286. /* function to open an output key file for this generation and file number...
  1287.  * use my Official Apple-Approved File Type 'CTLZ' (for control-Z = ^Z)...
  1288.  */
  1289.  
  1290. int open_outkfile (vRef0, generation_number, file_number)
  1291.   int vRef0, generation_number, file_number;
  1292.   {
  1293.     Str255 fname;
  1294.     int i;
  1295.     
  1296.     fname[1] = 'z';
  1297.     fname[2] = generation_number + 1 + '0';
  1298.     fname[3] = 'k';
  1299.     i = putNum ((char *)fname + 4, file_number / NMERGE);
  1300.     fname[0] = i + 3;
  1301.     if (Create (fname, vRef0, '????', 'CTLZ') != noErr)
  1302.       {
  1303.         give_msg ("\pSorry, fatal error creating merge key file -- click mouse to exit, then reboot!");
  1304.         beepWait ();
  1305.           RestoreA4();
  1306.         ExitToShell ();
  1307.       }
  1308.     
  1309.     if (FSOpen (fname, vRef0, &i) != noErr)
  1310.       {
  1311.         give_msg ("\pSorry, fatal error opening merge key file -- click mouse to exit, then reboot!");
  1312.         beepWait ();
  1313.           RestoreA4();
  1314.         ExitToShell ();
  1315.       }
  1316.  
  1317.     return (i);
  1318.   }
  1319.  
  1320.  
  1321. /* function to open an output ptr file for this generation and file number
  1322.  * again, use 'CTLZ' file type...
  1323.  */
  1324.  
  1325. int open_outpfile (vRef0, generation_number, file_number)
  1326.   int vRef0, generation_number, file_number;
  1327.   {
  1328.     Str255 fname;
  1329.     int i;
  1330.     
  1331.     fname[1] = 'z';
  1332.     fname[2] = generation_number + 1 + '0';
  1333.     fname[3] = 'p';
  1334.     i = putNum ((char *)fname + 4, file_number / NMERGE);
  1335.     fname[0] = i + 3;
  1336.     if (Create (fname, vRef0, '????', 'CTLZ') != noErr)
  1337.       {
  1338.         give_msg ("\pSorry, fatal error creating merge ptr file -- click mouse to exit, then reboot!");
  1339.         beepWait ();
  1340.           RestoreA4();
  1341.         ExitToShell ();
  1342.       }
  1343.     
  1344.     if (FSOpen (fname, vRef0, &i) != noErr)
  1345.       {
  1346.         give_msg ("\pSorry, fatal error opening merge ptr file -- click mouse to exit, then reboot!");
  1347.         beepWait ();
  1348.           RestoreA4();
  1349.         ExitToShell ();
  1350.       }
  1351.  
  1352.     return (i);
  1353.   }
  1354.  
  1355.  
  1356. /* function to rename the remaining last unpaired key file & ptr file
  1357.  * from one generation to the next...
  1358.  */
  1359.  
  1360. void fix_oddball_file_name (vRef0, generation_number, file_number)
  1361.   int vRef0, generation_number, file_number;
  1362.   {
  1363.     Str255 oldname, newname;
  1364.     int i;
  1365.     
  1366.     oldname[1] = 'z';
  1367.     oldname[2] = generation_number + '0';
  1368.     oldname[3] = 'k';
  1369.     i = putNum ((char *)oldname + 4, file_number);
  1370.     oldname[0] = i + 3;
  1371.  
  1372.     newname[1] = 'z';
  1373.     newname[2] = generation_number + 1 + '0';
  1374.     newname[3] = 'k';
  1375.     i = putNum ((char *)newname + 4, file_number / NMERGE);
  1376.     newname[0] = i + 3;
  1377.     
  1378.     if (Rename (oldname, vRef0, newname) != noErr)
  1379.       {
  1380.         give_msg ("\pSorry, error renaming merge key file ... click mouse to continue");
  1381.         beepWait ();
  1382.       }
  1383.     
  1384.     oldname[1] = 'z';
  1385.     oldname[2] = generation_number + '0';
  1386.     oldname[3] = 'p';
  1387.     i = putNum ((char *)oldname + 4, file_number);
  1388.     oldname[0] = i + 3;
  1389.  
  1390.     newname[1] = 'z';
  1391.     newname[2] = generation_number + 1 + '0';
  1392.     newname[3] = 'p';
  1393.     i = putNum ((char *)newname + 4, file_number / NMERGE);
  1394.     newname[0] = i + 3;
  1395.     
  1396.     if (Rename (oldname, vRef0, newname) != noErr)
  1397.       {
  1398.         give_msg ("\pSorry, error renaming merge ptr file ... click mouse to continue");
  1399.         beepWait ();
  1400.       }
  1401.  
  1402.     return;
  1403.   }
  1404.  
  1405.  
  1406. /* function to give the final key and ptr files their proper ultimate
  1407.  * names ... ok for it to mess with doc_filename string....
  1408.  */
  1409.  
  1410. void fix_final_file_names (doc_filename, vRef0, generation_number)
  1411.   Str255 doc_filename;
  1412.   int vRef0, generation_number;
  1413.   {
  1414.     Str255 oldname;
  1415.     
  1416.     oldname[0] = 4;
  1417.     oldname[1] = 'z';
  1418.     oldname[2] = generation_number + '0';
  1419.     oldname[3] = 'k';
  1420.     oldname[4] = '0';
  1421.  
  1422.     doc_filename[++doc_filename[0]] = '.';
  1423.     doc_filename[++doc_filename[0]] = 'k';
  1424.     
  1425.     if (Rename (oldname, vRef0, doc_filename) != noErr)
  1426.       {
  1427.         give_msg ("\pSorry, error renaming final key file ... click mouse to continue");
  1428.         beepWait ();
  1429.       }
  1430.  
  1431.     oldname[3] = 'p';
  1432.     doc_filename[doc_filename[0]] = 'p';
  1433.  
  1434.     if (Rename (oldname, vRef0, doc_filename) != noErr)
  1435.       {
  1436.         give_msg ("\pSorry, error renaming final ptr file ... click mouse to continue");
  1437.         beepWait ();
  1438.       }
  1439.  
  1440.     return;
  1441.   }
  1442.  
  1443.  
  1444. /* function to get rid of the superfluous k & p files now that they
  1445.  * have been merged into the next generation....
  1446.  */
  1447.  
  1448. void remove_used_infiles (n, vRef0, generation_number, file_number)
  1449.   int n, vRef0, generation_number, file_number;
  1450.   {
  1451.     Str255 fname;
  1452.     int i, j;
  1453.     
  1454.     fname[1] = 'z';
  1455.     fname[2] = generation_number + '0';
  1456.     for (i = 0; i < n; ++i)
  1457.       {
  1458.         fname[3] = 'k';
  1459.         j = putNum ((char *)fname + 4, file_number + i);
  1460.         fname[0] = j + 3;
  1461.         
  1462.         if (FSDelete (fname, vRef0) != noErr)
  1463.           {
  1464.             give_msg ("\pSorry, error deleting merge key file ... click mouse to continue");
  1465.             beepWait ();
  1466.           }
  1467.  
  1468.         fname[3] = 'p';
  1469.         if (FSDelete (fname, vRef0) != noErr)
  1470.           {
  1471.             give_msg ("\pSorry, error deleting merge ptr file ... click mouse to continue");
  1472.             beepWait ();
  1473.           }
  1474.       }
  1475.     
  1476.     return;
  1477.   }
  1478.  
  1479.  
  1480. /* function to close out the ink and inp files that have been opened...
  1481.  */
  1482.  
  1483. void close_infiles (ink, inp, n)
  1484.   int ink[], inp[];
  1485.   int n;
  1486.   {
  1487.     int i;
  1488.     
  1489.     for (i = 0; i < n; ++i)
  1490.       {
  1491.         FSClose (ink[i]);
  1492.         FSClose (inp[i]);
  1493.       }
  1494.   }
  1495.  
  1496.  
  1497. /* function to open the key file with proper name for this pass ... file will be
  1498.  * named "z0kN" where N represents the pass number .... type 'CTLZ'
  1499.  */
  1500.  
  1501. int open_kfile (vRef0, pass_number)
  1502.   int vRef0, pass_number;
  1503.   {
  1504.     Str255 fname;
  1505.     int i;
  1506.     
  1507.     fname[1] = 'z';
  1508.     fname[2] = '0';
  1509.     fname[3] = 'k';
  1510.     i = putNum ((char *)fname + 4, pass_number);
  1511.     fname[0] = i + 3;
  1512.     
  1513.     if (Create (fname, vRef0, '????', 'CTLZ') != noErr)
  1514.       {
  1515.         give_msg ("\pSorry, fatal error creating key file -- click mouse to exit, then reboot!");
  1516.         beepWait ();
  1517.           RestoreA4();
  1518.         ExitToShell ();
  1519.       }
  1520.     
  1521.     if (FSOpen (fname, vRef0, &i) != noErr)
  1522.       {
  1523.         give_msg ("\pSorry, fatal error opening key file -- click mouse to exit, then reboot!");
  1524.         beepWait ();
  1525.           RestoreA4();
  1526.         ExitToShell ();
  1527.       }
  1528.  
  1529.     return (i);
  1530.   }
  1531.  
  1532.  
  1533. /* function to open the ptr file with proper name for this pass ... file will be
  1534.  * named "z0pN" where N represents the pass number .... type 'CTLZ'
  1535.  */
  1536.  
  1537. int open_pfile (vRef0, pass_number)
  1538.   int vRef0, pass_number;
  1539.   {
  1540.     Str255 fname;
  1541.     int i;
  1542.     
  1543.     fname[1] = 'z';
  1544.     fname[2] = '0';
  1545.     fname[3] = 'p';
  1546.     i = putNum ((char *)fname + 4, pass_number);
  1547.     fname[0] = i + 3;
  1548.     if (Create (&fname, vRef0, '????', 'CTLZ') != noErr)
  1549.       {
  1550.         give_msg ("\pSorry, fatal error creating ptr file -- click mouse to exit, then reboot!");
  1551.         beepWait ();
  1552.           RestoreA4();
  1553.         ExitToShell ();
  1554.       }
  1555.     
  1556.     if (FSOpen (&fname, vRef0, &i) != noErr)
  1557.       {
  1558.         give_msg ("\pSorry, fatal error opening ptr file -- click mouse to exit, then reboot!");
  1559.         beepWait ();
  1560.           RestoreA4();
  1561.         ExitToShell ();
  1562.       }
  1563.  
  1564.     return (i);
  1565.   }
  1566.  
  1567.  
  1568. /* function to take the place of stdio's ftell()
  1569.  */
  1570.  
  1571. long zftell (refnum)
  1572.   int refnum;
  1573.   {
  1574.     long ans;
  1575.     
  1576.     GetFPos (refnum, &ans);
  1577.     return (ans);
  1578.   }
  1579.  
  1580.  
  1581. /* --------------function to do quicksort -------------------------- */
  1582.  
  1583. /*  sort elements "first" through "last" */
  1584.  
  1585. void zqsort (first, last)
  1586.   register char **first, **last;
  1587.   {
  1588.     register char **i, **j, *tmp;
  1589.  
  1590.     while (last - first > 1)
  1591.       {
  1592.         i = first;
  1593.         j = last;
  1594.         for (;;)
  1595.           {
  1596.             while (++i < last && compare_ptrs (i, first) < 0)
  1597.                 ;
  1598.             while (--j > first && compare_ptrs (j, first) > 0)
  1599.                 ;
  1600.             if (i >= j)
  1601.                  break;
  1602.              tmp = *i;
  1603.              *i = *j;
  1604.              *j = tmp;
  1605.           }
  1606.         tmp = *first;
  1607.         *first = *j;
  1608.         *j = tmp;
  1609.         if (j - first < last - (j + 1))
  1610.           {
  1611.             zqsort (first, j);
  1612.             first = j + 1;
  1613.           }
  1614.         else
  1615.           {
  1616.             zqsort (j + 1, last);
  1617.             last = j;
  1618.           }
  1619.       }
  1620.   }
  1621.  
  1622.  
  1623. /* function to compare two index ptrs and give a result appropriate
  1624.  * for quicksort to use in alphabetizing them....
  1625.  *
  1626.  * Since the words pointed to have already been turned into all capital
  1627.  * letters and delimiters have been filtered out, simply doing zstrcmp()
  1628.  * for KEY_LENGTH letters works fine!
  1629.  *
  1630.  * Slight modification to make the quicksort stable:  if two words tie,
  1631.  * then we want to compare their pointers to make the lesser one come
  1632.  * out first in the sort ...
  1633.  */
  1634.  
  1635. int compare_ptrs (p1, p2)
  1636.   register char **p1, **p2;
  1637.   {
  1638.     register int diff;
  1639.     
  1640.     diff = zstrcmp (*p1, *p2);
  1641.     if (diff == 0)
  1642.         diff = ((*p1 - *p2) > 0) ? 1 : -1;
  1643.     return (diff);
  1644.   }
  1645.  
  1646.  
  1647.  
  1648. /* my function to compare two strings and give a result as to who is
  1649.  * alphabetically earlier.  Note that this is almost the same as strncmp()
  1650.  * with the fixed value of KEY_LENGTH as the maximum comparison distance,
  1651.  * except that I must be sure to mask the characters to make them positive
  1652.  * (since we want to be able to handle the non-ASCII funny letters in
  1653.  * the Apple character set properly/consistently).  If the masking isn't
  1654.  * done, then inconsistent results can occur with those non-ASCII chars!
  1655.  */
  1656.  
  1657. int zstrcmp (s1, s2)
  1658.   register char *s1, *s2;
  1659.   {
  1660.     register int n = KEY_LENGTH;
  1661.     
  1662.     for (; --n && ((*s1 & 0xFF) == (*s2 & 0xFF)); s1++, s2++)
  1663.         if (!*s1) break;
  1664.         
  1665.     return ((*s1 & 0xFF) - (*s2 & 0xFF));
  1666.   }
  1667.  
  1668.